// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-10 14:52
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.DataStruct.Tree.TwoBinaryTree;

import java.util.Arrays;

@SuppressWarnings("ALL")
/**
 * 获取给定二叉树直径方法
 * 使用的是方法二，时间复杂度为O(N)
 * 方法存储图的信息使用了链式前向星
 */
public class TreeDiameter {
    // maxn记录点的个数
    final int maxn = (int) 1e4 + 5;
    // 记录边的个数
    Edge[] edges = new Edge[2 * maxn];
    int[] head = new int[maxn];

    {
        // 对head数组进行初始化，表示根节点或空节点的父节点为-1
        Arrays.fill(head, -1);
    }

    int maxdis, maxv, idx = 0;

    /**
     * 边信息初始化方法
     *
     * @param u: 起点
     * @param v: 终点
     * @param w: 边权值
     */
    void add(int u, int v, int w) {
        edges[idx] = new Edge(v, head[u], w);
        head[u] = idx++;
    }


    /**
     * 深度优先遍历记录最长距离
     *
     * @param u:       起点
     * @param fa:u的父节点
     * @param d2s:     u点到原点的距离
     */
    void dfs(int u, int fa, int d2s) {
        if (maxdis < d2s) {
            // dfs 方法的真正目的
            maxdis = d2s;
            maxv = u;
        }
        // 循环一次遍历一个点的所有边信息
        for (int e = head[u]; e != -1; e = edges[e].next) {
            int v = edges[e].to, w = edges[e].weight;
            if (v == fa) {
                // 避免重复遍历父节点，孩子节点不会被重复遍历
                continue;
            }
            dfs(v, u, d2s + w);
        }
    }

    /**
     * 边信息类
     */
    class Edge {
        int to, next, weight;

        public Edge(int to, int next, int weight) {
            this.to = to;
            this.next = next;
            this.weight = weight;
        }
    }

    /**
     * 方法测试
     *
     * @param args
     */
    public static void main(String[] args) {
        int[][] es = {{0, 1, 1}, {0, 2, 4}, {1, 3, 1}, {1, 4, 1}};
        TreeDiameter td = new TreeDiameter();
        // 初始化边信息
        for (int[] e : es) {
            td.add(e[0], e[1], e[2]);
            td.add(e[1], e[0], e[2]);
        }
        // 第一次dfs
        td.dfs(0, -1, 0);
        // 第二次dfs
        td.maxdis = 0;
        td.dfs(td.maxv, -1, 0);
        System.out.println(td.maxdis);
    }

}
